package dp

// 分割成两个子集，使得子集元素和相等
func canPartition(nums []int) bool {
	// 先判断总和是否是偶数
	sum := 0 
	for i:=range nums {
		sum += nums[i]
	}
	if sum%2!=0 {
		return false
	}
	// 为偶数 则可能
	// 搜索，搜索到一个和为sum/2的
	// 背包问题，背包容量为sum/2 ，重量和价值皆为nums[j]  判断条件变了，不是求最大价值
	// dp[j] 表示容量为j的背包，价值最大可以为dp[j]
	// dp[j] = max(dp[j]  dp[j-nums[i]]+nums[i])
	dp := make([]int, sum/2+1)
	// 初始化 
	dp[0] = 0
	// 确定遍历顺序
	target := sum/2
	for i:=0;i<len(nums);i++ {  //遍历物品
		// 背包容量 从后   元素不可重复放入
		for j:= target;j>=nums[i];j-- {
			dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
		}
	}
	return dp[target] == target
}
func max(a,b int) int {
	if a>b {return a}
	return b
}